package day35;
import java.util.*;

public class A3 {


    /**
     * 动态规划dp，两个字符串的问题，根据最后一个字符划分问题
     * @param args
     */

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s = in.nextLine();
            String t = in.nextLine();
            int n=s.length(),m=t.length();
            int[][] dp = new int[n+1][m+1];
            s = " "+s;
            t = " "+t;
            dp[0][0]=0;
            for(int i=1;i<=n;i++) dp[i][0]=i;
            for(int i=1;i<=m;i++) dp[0][i]=i;
            for(int i=1;i<=n;i++) {
                for(int j=1;j<=m;j++) {
                    if(s.charAt(i)==t.charAt(j)) {
                        dp[i][j]=dp[i-1][j-1];
                    }else {
                        dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                    }
                }
            }
            System.out.println(dp[n][m]);
        }
    }
}
